
\section{\label{sec:Finite-Time-Distributed-Consensu}Finite-Time Distributed
Consensus Algorithm}

Finite-Time Distributed Consensus Algorithm (FT-DCA) is an non-asymptotic
algorithm. It tries to find the consensus value after each node run
the FO-DCA algorithm iteratively for a certain number of time. This
is based on the assumption that after a certain number of iterations,
local values would contain sufficient information to estimate the
consensus value. (OK2.5)
\begin{defn}
Given the network $\mathcal{G}$, and initial local value vector $\mathbf{x}\left(0\right)$,
it is said the algorithm achieves a finite-time consensus if it solves
a consensus problem, and there exist a time $t^{*}$ and the consensus
value $\bar{x}$ such that $x_{i}\left(t\right)=\bar{x}$, for all
time $t>t^{*}$. 
\end{defn}
Motivated by the works in \cite{Kokiopoulou2007}, we try to decompose
the local value vector in a form which reveals an important property
of its iteration. Therefore we propose a filtering technique to estimate
the consensus value. 


\subsection{\label{sub:Find_Consensus_Value}Find the Consensus Value by Linear
Filter}

In the network that adopts first order linear consensus algorithm,
each node has a number of consecutive local values obtained by Eq.\prettyref{eq:1st iter. ni}.
There exists a linear filter. If each node passes its consecutive
local values through this filter, the output after a certain time
is the global average of the initial values over the network. Compared
to first order DCA algorithm, no more information exchanged between
nodes is needed. Such a filter is defined as the \textit{consensus
finding filter}. 
\begin{thm}
\label{thm.A-consensus-finding}There exists a linear filter defined
by $\mathbf{h}\in R^{d}$, such that by passing through local values
\textup{$x_{i}(k)$} \textup{obtained by Eq.\prettyref{eq:1st iter. ni},
}the output \textup{$\hat{x}_{i}(k)=\mathbf{h}(k)*x_{i}(k)$} is the
consensus value \textup{$\overline{x}=\frac{1}{n}\sum_{i=1}^{n}x_{i}(0)$}
of the network after $k$ step $\left(k\geqslant m\right)$, where
\textup{$m$ is the number of} distinct and nonzero eigenvalues of
the weight matrix $W$ and $W$ satisfies the convergence condition\textup{
\ref{eq:convege condition W}. }\end{thm}
\begin{proof}
To avoid complicate analysis, suppose an undirected network with $n$
nodes, where duplex communication is possible in each link. Therefore,
the associated weight matrix $W\in\mathbf{R}^{n\times n}$ is symmetric
and diagonalizable. W Thus, there are $n$ linear independent eigenvectors
of the weight matrix. Let $\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{n}$
be the eigenvectors of $W$ and $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$
be the associated eigenvalues. They are ordered so that $1=\left|\lambda_{1}\right|\geq\left|\lambda_{2}\right|\geq\ldots\geq\left|\lambda_{n}\right|$.
$\lambda_{1}$ is called the dominant eigenvalue and $\mathbf{e}_{1}$
is associated dominant eigenvector.Since all the eigenvectors consist
a basis of $\mathbf{R}^{n}$, any initial value vector can be written
in a linear combination of these eigenvectors, 

\begin{equation}
\mathbf{x}\left(0\right)=\alpha_{1}\mathbf{e}_{1}+\alpha_{2}\mathbf{e}_{2}+\ldots+\alpha_{n}\mathbf{e}_{n}
\end{equation}
where $\alpha_{i}(i=1,2,\ldots,n)$ is the coefficient. For $k=1,2,3,...$
we have

\begin{eqnarray}
\mathbf{x}\left(k\right) & = & W^{k}\left[\alpha_{1}\mathbf{e}_{1}+\alpha_{2}\mathbf{e}_{2}+\ldots+\alpha_{n}\mathbf{e}_{n}\right]\nonumber \\
 & = & \alpha_{1}\lambda_{1}^{k}\mathbf{e}_{1}+\alpha_{2}\lambda_{2}^{k}\mathbf{e}_{2}+\ldots+\alpha_{n}\lambda_{n}^{k}\mathbf{e}_{n}\label{eq:x(k) decomposition}\\
 & = & \sum_{i=1}^{n}\alpha_{i}\lambda_{i}^{k}\mathbf{e}_{i}\nonumber 
\end{eqnarray}
where $\lambda_{i}$ is the eigenvalue of $W$. 

By rewriting $\mathbf{x}\left(k\right)$, it is clear that if all
eigenvalues of the weight matrix are known, the node values vector
is predictable and the consensus value can be found. For any node
$i=1,2,\ldots n$, its local value at time $k$ can be written as
\begin{equation}
x_{i}\left(k\right)=\alpha_{1}\lambda_{1}^{k}e_{i1}+\alpha_{2}\lambda_{2}^{k}e_{i2}+\ldots+\alpha_{n}\lambda_{n}^{k}e_{in}
\end{equation}
where $e_{ij}$ is the $i^{th}$ component of eigenvector $\mathbf{e}_{j}$.
Because of algebraic multiplicity of some eigenvalues, the equation
can be modified by combining the terms with the same eigenvalues.
Zero eigenvalues are ignored as they have no contribution in this
equation. Suppose $W$ has $m$ distinct and nonzero eigenvalues,
denoted by $\lambda_{1},\lambda_{2},\ldots,\lambda_{m}$, then $x_{i}\left(k\right)$
evolves into 
\begin{equation}
x_{i}\left(k\right)=\beta_{i1}\lambda_{1}^{k}+\beta_{i2}\lambda_{2}^{k}+\ldots+\beta_{im}\lambda_{m}^{k}
\end{equation}
where $\beta_{ij}$ is the coefficient after combination. 

Let the sample vector $\mathbf{y}_{i}(k,d)\in R^{d}$ is defined by
the history of $x_{i}(k),$ 

\begin{equation}
\mathbf{y}_{i}(k,d)=\left[x_{i}(k),x_{i}(k+1),\ldots x_{i}(k+d-1)\right]^{\mathrm{T}}\label{eq:def. y(k,m)}
\end{equation}
and the Vandermonde matrix whose entries are the power of eigenvalues

\begin{equation}
\mathbf{V}(k,d)=\left[\begin{array}{cccc}
\lambda_{1}^{k} & \lambda_{2}^{k} & \cdots & \lambda_{m}^{k}\\
\lambda_{1}^{k+1} & \lambda_{2}^{k+1} & \cdots & \lambda_{m}^{k+1}\\
\vdots & \vdots & \ddots & \vdots\\
\lambda_{1}^{k+d-1} & \lambda_{2}^{k+d-1} & \cdots & \lambda_{m}^{k+d-1}
\end{array}\right]\label{eq:def. Lamda(k,m)}
\end{equation}
and $\mathbf{b}_{i}\left(d\right)=\left[\beta_{i1},\beta_{i2},\cdots\beta_{id}\right]^{\mathrm{T}}$,
then we have the following equation satisfied

\begin{equation}
\mathbf{y}_{i}(k,d)=\mathbf{V}(k,d)\mathbf{b}_{i}\left(d\right)\label{eq:Vander_beta}
\end{equation}
To obtain the consensus value $\bar{x}$ for node $i$, we need to
take sufficient samples of $x_{i}(k)$\textbf{ }and solve Eq.\prettyref{eq:Vander_beta},
where $d$ should at least equal or larger than\textbf{ $m$}, which
is the number of distinct and nonzero eigenvalues of weight matrix
$W$

Let $A(k,m)=\mathbf{V}^{-1}(k,m)$ and the first row of $A(k,m)$
is given by 
\begin{equation}
\mathbf{h}=\left[A_{11}(k,m),A_{12}(k,m),\ldots,A_{1m}(k,m)\right]^{\mathrm{T}}
\end{equation}
 we have 

\begin{equation}
\beta_{i1}=\mathbf{h}^{\mathrm{T}}\mathbf{y}_{i}(k,m)\label{eq:Find Consensus m order}
\end{equation}
 Eq.\prettyref{eq:Find Consensus m order} shows that the consensus
value can be calculated by the filter defined in Def.\ref{thm.A-consensus-finding}.
This ends the proof.
\end{proof}
It is worth noting that Vandermonde matrix is related to a polynomial
interpolation problem and can be easily inverted in terms of Lagrange
basis polynomials \cite{Prass2007}. Due to this reason, this method
can be treated as an extrapolation method which find the consensus
value at infinity. At the same time, we only need to find out the
first coefficient $\beta_{i1}$ in the distributed averaging. Therefore,
only the elements in the corresponding row of $\mathbf{V}^{-1}(k,m)$
need to be found. This approach can save lots of computation time
in the inverting of Vandermonde matrix. 

Since simulation result shows that $\mathbf{h}$ is only depends the
associated Vandermonde matrix $\mathbf{V}(k,m)$ which is independent
of the nodes initial values and time index $k$. Therefore, each node
in the network could find the consensus value at any time $k\geqslant m$
by passing a number of consecutive local values through this filter.
In addition, all nodes in this network may share the same filter,
which means all the filters have the same impulse response. However,
such a consensus finding filter it is not unique. As an example, a
number of filters which have different impulse response or filter
lengths are found by different samples of $x_{i}(k)$.  Each node
could choose its own, but filter length determines the how many time-steps
before a node could find the consensus value. 

Suppose we take $d$ samples of $x_{i}(k)$, where $d>m$. Because
the Vandermonde matrix $\mathbf{V}(k,d)\in R^{d\times m}$ is non-square,
we introduce the Moore-Penrose pseudo inverse to find the least mean
square solution. 

Let

\begin{equation}
A(k,d)=\mathbf{V}^{+}(k,d)
\end{equation}
where $^{+}$ denote the Moore-Penrose pseudo inverse \cite{Piziak2007}.
And the first row of $A(k,d)$ is given by 

\begin{equation}
\mathbf{h}'=\left[A{}_{11}(k,d),A_{12}(k,d),\ldots,A_{1d}(k,d)\right]^{\mathrm{T}}
\end{equation}
Still, the value $\beta_{i1}=\mathbf{h}'^{\mathrm{T}}\mathbf{y}_{i}(k,m)$
is an accurate estimation of consensus value. Therefore, another consensus
finding filter is obtained.

Due to the multiplication of the consensus finding filter, the set
of filter is defined by

\begin{equation}
\{\mathbf{h}\in R^{d}|\forall d\geqslant m,\:\mathbf{h}^{\mathrm{T}}\mathbf{y}_{i}(k,d)=\bar{x}\}
\end{equation}
However, the shortest filter has its length equal to $m$, which means
node can only have the consensus value after $m$ steps. 

In \prettyref{sub:Numerical-Simulation}, the performance of this
algorithm is shown by comparing it with the first order DAC algorithm
using optimal weight matrix in \cite{Xiao2004}.


\subsection{Inverse the Vandermonde matrix}

The Vandermonde matrix has its application in some problems like polynomial
fitting, reconstruction of distributions from their moments, and so
on. Solving Vandermonde matrix is related to a polynomial interpolation
problem and can be easily inverted in terms of Lagrange basis polynomials.
It can be very difficult to invert in other way if the size of the
matrix is large, as the Vandermonde matrix is notoriously ill-conditioned
by its nature. It is a good way to always work on the problems related
to Vandermonde matrix in double precision or higher. 

Let $V_{m}$ be the Vandermonde's matrix of order $m$ given by 

\begin{equation}
V_{m}=\left[\begin{array}{cccc}
\lambda_{1} & \lambda_{2} & \cdots & \lambda_{m}\\
\lambda_{1}^{2} & \lambda_{2}^{2} & \cdots & \lambda_{m}^{2}\\
\vdots & \vdots & \ddots & \vdots\\
\lambda_{1}^{m} & \lambda_{2}^{m} & \cdots & \lambda_{m}^{m}
\end{array}\right]\label{eq:Vander Matrix}
\end{equation}
Then the equation 
\begin{equation}
\left[\begin{array}{cccc}
\lambda_{1} & \lambda_{2} & \cdots & \lambda_{m}\\
\lambda_{1}^{2} & \lambda_{2}^{2} & \cdots & \lambda_{m}^{2}\\
\vdots & \vdots & \ddots & \vdots\\
\lambda_{1}^{m} & \lambda_{2}^{m} & \cdots & \lambda_{m}^{m}
\end{array}\right]\left[\begin{array}{c}
\beta_{1}\\
\beta_{2}\\
\vdots\\
\beta_{m}
\end{array}\right]=\left[\begin{array}{c}
y_{1}\\
y_{2}\\
\vdots\\
y_{m}
\end{array}\right]\label{eq:Vander Eq.}
\end{equation}
is related to the problem of moments: Given the values of all $\lambda_{i}$,
find the unknown coefficients $b_{i}$, so that they match the given
values $y_{i}$ of the first $m$ moments. 

Its inverse is closely related to Lagrange's polynomial interpolation
formula. 

Let the polynomial of degree $m$ defined by 
\begin{equation}
P_{j}\left(\lambda\right)=\prod_{\begin{array}{c}
i=1\\
i\neq j
\end{array}}^{m}\frac{\lambda-\lambda_{i}}{\lambda_{j}-\lambda_{i}}=\sum_{k=1}^{m}b_{jk}\lambda^{k-1}\label{eq:Lagrange's polynomial}
\end{equation}
The polynomial $P_{j}\left(\lambda\right)$ a function of $\lambda$
and is specially designed so that it is equal to zero at all $\lambda_{i}$
except $i=j$ and takes on a value of one at $\lambda=\lambda_{j}$.
In other words, 
\[
P_{j}\left(\lambda_{i}\right)=\delta_{ij}=\sum_{k=1}^{m}b_{jk}\lambda_{i}^{k-1}
\]
where $\delta_{ij}=1$ when $i=j$. The equation says that $b_{jk}$
is exactly the inverse of the matrix \prettyref{eq:Vander Matrix},
with the subscript $k$ as the column index. 

To drive the analytical expression of $b_{jk}$ and make it as easy
as possible, let's define some intermediate result. Define the polynomial
$q_{j}\left(\lambda\right)$ and work out its coefficients

\begin{eqnarray}
q_{j}\left(\lambda\right) & = & \frac{\prod_{i=1}^{m}\left(\lambda-\lambda_{i}\right)}{\left(\lambda-\lambda_{j}\right)}=\prod_{i=1,i\neq j}^{m}\left(\lambda-\lambda_{i}\right)\label{eq:intermindia polynomial}\\
 & = & c_{j,m}\lambda^{m-1}+c_{j,m-1}\lambda^{m-2}+\ldots+c_{j,2}\lambda+c_{j,1}\nonumber 
\end{eqnarray}
Examining the polynomial \ref{eq:Lagrange's polynomial} and polynomial
\ref{eq:intermindia polynomial}, we have 
\begin{eqnarray*}
b_{jk} & = & \frac{c_{j,m}}{q_{j}\left(\lambda_{j}\right)}
\end{eqnarray*}
Therefore, the solution of Eq.\ref{eq:Vander Eq.} is just the inverse
of Vandermonde matrix time the vector on the right. 
\[
\beta_{j}=\sum_{k=1}^{m}b_{jk}y_{k}
\]
If we only need to calculate the consensus value, as explained in
\ref{sub:Find_Consensus_Value} only the elements in the corresponding
row of inverse Vandermonde's matrix need to be found. The computation
saving can be enormous by this approach.
